package com.origin.niuke.linkedlist;

import general_class.ListNode;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/4/28 10:45
 * 链表相加(二)
 * 假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
 * 给定两个这种链表，请生成代表两个整数相加值的结果链表。
 * 算法：链表 + 模拟
 */
public class NC40 {

    public ListNode addInList(ListNode head1, ListNode head2) {
        head1 = reverse(head1);
        head2 = reverse(head2);
        ListNode ans = new ListNode(-1), cur = ans;
        int carry = 0;
        while (head1 != null || head2 != null) {
            int a = head1 != null ? head1.val : 0;
            int b = head2 != null ? head2.val : 0;
            int tmp = a + b + carry;
            cur.next = new ListNode(tmp % 10);
            carry = tmp / 10;
            cur = cur.next;
            if (head1 != null) head1 = head1.next;
            if (head2 != null) head2 = head2.next;
        }
        if (carry == 1) cur.next = new ListNode(1);
        return reverse(ans.next);
    }

    ListNode reverse(ListNode node) {
        ListNode pre = null;
        while (node != null) {
            ListNode next = node.next;
            node.next = pre;
            pre = node;
            node = next;
        }
        return pre;
    }

}
